The present invention relates to data processing and, more particularly, to data compression. Certain embodiments of the invention provide for high-speed, high-quality, single-pass, guaranteed-fit, compression of continuous-tone compound documents (containing an arbitrary combination of text, graphics and photographic images).
Much of modern progress is associated with advances in computer technology, which have permitted ever more rapid and complex data processing. However, the amounts of data to be processed have easily kept pace with the increases in processing power. For example, scanning an 8×10 image at 24-bit color (continuous-tone) resolution and 300 dots per inch (dpi) results in about 20 MB of data. If the resolution is 600 dpi, the quantity of data is close to 80 MB, making image handling and processing a resource-intensive task.
In many applications, data compression is used to reduce the amount data required to represent an image. Data compression is the re-encoding of data in a more compact form. If the compressed data can be expanded to replicate the original (uncompressed) data, the compression is said to be “lossless”. If this is not possible, the compression is said to be lossy. While lossless compression is preferable in principle, lossy compression can often achieve dramatically greater reductions in data. In the case of some images, dramatic reductions in data can be achieved using lossy compression with no perceptible loss of image quality. In other cases, even more dramatic reductions can be achieved with acceptable compromises in image quality.
In some applications, such as some laser printing applications, there is insufficient memory to store a full-size uncompressed image. In such applications, the image must be compressed so that the entire compressed image fits within a predetermined memory size. A compression scheme that guarantees that a target image size will be met is characterized as “guaranteed fit”. Furthermore, from considerations of fast operation and low memory requirements, it must also be compressed as it is received, i.e., in a “single pass”.
Not all image compression schemes are suitable for single-pass guaranteed-fit applications. The wavelet-based JPEG 2000 can guarantee a fit, but typically operates on an entire image (and so does not qualify as “single pass”); in addition, wavelet-based compression schemes are processor intensive and so exact a performance penalty.
Block-based compression schemes are well-suited for single-pass compression. Block-based compression schemes typically break an image into blocks, (e.g., 8×8 pixels) and compress the blocks individually. Common JPEG and block-truncation coding (BTC) are two such block-based compression schemes.
The popular JPEG compression scheme is block-based and as such can be used for single pass compression, but it provides no guarantee of fit in a designated buffer in a single pass; also, for rare pathological images it may even expand rather than compress.
“Block Truncation Coding” (BTC) (first proposed by E. J. Delp and O. R. Mitchell, “Image Compression using block truncation coding,” IEE Trans. Comm., vol. COM-27, pp. 1335–42, 1979) refers to a family of coding techniques where small blocks (typically 4×4) of monochrome images are represented with two grayscale levels 8 bits each, and a 1-bit/pixel binary mask denoting the level to use for each pixel. While the coding scheme is lossy in principle, it is to be noted that for blocks with only two levels—as is commonly encountered in text and graphics portions of an image—the scheme becomes lossless. A comprehensive survey of BTC encoding is presented by P. Franti, O. Nevalainen, T. Kaukoranta, “Compression of digital Images by block truncation coding: a survey,” Computer Journal, col. 37, no. 4, pp. 308–32, 1994.
Vector Quantization (VQ) refers to a popular signal compression scheme where multiple scalar elements are grouped together and reproduced using a few vector reproduction levels. VQ is discussed in A. Gersho and R. M. Gray, Vector Quantization and Signal Compression, Boston, Mass.: Kluwer, 1992. For RGB color images, BTC may be combined with VQ to yield a family of techniques called BTC-VQ, as disclosed in Y. Wu and D. C. Coll, “Single bit-map block truncation coding of color images,” IEEE J. Selected Areas in Comm., vol. 10, pp. 952–959, and in T. Kurita and N. Otsu, “A method for block truncation coding for color image compression,” IEEE trans. Commun., vol. 41, no. 9, pp. 1270–74, September 1993. In BTC-VQ, small blocks (typically 4×4) of RGB color images are represented with two RGB reproduction levels 24 bits each, and a 1-bit/pixel binary mask. Thus, a compression ratio of 6:1 is immediately achieved for 4×4 blocks.
BTC-VQ can achieve single-pass guaranteed fit corresponding to 6:1 compression using 8×8 blocks, and greater guaranteed fit compression using larger blocks. However, BTC-VQ can result in visible artifacts in continuous-tone photographic images, especially if more than 6:1 compression is desired, forcing using of larger blocks.
Common JPEG is a block-based compression scheme that works well with continuous tone photographic images. JPEG allows a flexible tradeoff between compression and resulting image quality via selection of a “quality factor”. Normally, a guaranteed fit is achieved in JPEG by trial-and-error selection of quality factors, with each “trial” being a separate pass. To accomplish guaranteed fit in one pass regardless of the image, a sufficiently low quality factor must be selected. With such a low quality factor, the resulting image quality can be visibly degraded, especially in text and graphics portions of compound documents.
Some optical character recognition and other programs, such as Omnipage by Caere, divide an image into text and non-text blocks via a prescan so that the two types of blocks can be treated separately. However, such prescan techniques do not meet the single-pass requirement. Accordingly, there is still a need for a high-quality, high-speed, single-pass, guaranteed-fit compression scheme for compound documents.